#include <iostream>

using namespace std;

class Solution
{
public:
    int totalNQueens(int n)
    {
        unsigned int pl = 0, pr = 0, ps = 0; // 0:placeable, 1:unplaceable
        int count = 0;
        LevelOP(1, pl, pr, ps, n, count);
        return count;
    }

    void LevelOP(int level, unsigned int pl, unsigned int pr, unsigned int ps, int n, int &count)
    {
        unsigned int curPlaceable = pl << 1 | pr >> 1 | ps;
        for (int x = 0; x < n; x++)
        {
            // try place queen at level y, index x
            if (curPlaceable & (1 << x))
                continue;
            else
            {
                if (level == n)
                    count++;
                else
                    LevelOP(level + 1, (pl << 1) | (1 << x), (pr >> 1) | (1 << x), ps | (1 << x), n, count);
            }
        }
    }
};

int main()
{
    cout << "Code52" << endl;
    Solution s;
    cout << s.totalNQueens(4) << endl;
    return 0;
}